1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for implementing FIFOs in shared memory using linked lists and interleaved linked lists.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled together and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as data frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
A network element may have many ports, each of which may maintain multiple data queues. For example, a network element may maintain an input queue at an input port for each output port, each flow, or in a number of other manners. Maintaining different queues for different classes or types of traffic allows the network element to treat the different classes of traffic differently. Queuing at the input port allows data received over the port to be held until the output port is ready to output the data. In a conventional system, each queue is typically configured as a First In First Out (FIFO) queue which is statically allocated a particular range of memory locations in a common memory.
The static allocation of memory to queues requires the network element to have a large amount of memory to implement the queues. Specifically, not every port on a network element may be receiving data at the same rate. In this instance, a particular FIFO may fill to the point where it is unable to store additional protocol data units and will need to start dropping protocol data units, even though other FIFOs remain relatively empty. To accommodate reasonably large bursts of data, the memory must be increased to be able to allocate sufficient memory to each queue. As the number of queues grows, to allow the network element to assert increased control over the traffic, the memory requirements grow accordingly. While it would be desirable to allow the FIFOs on a network element to dynamically adjust their size as their needs changed, implementing FIFOs with an adjustable size has conventionally been unfeasible in hardware. Since the rate at which data arrives on a network element is quite high, implementing a software solution or moving data around within the memory to accommodate the new FIFO size demarcations is generally not a practicable solution.